// 树的子结构： https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func isSubStructure(A *TreeNode, B *TreeNode) bool {
	// 1. 如果是空树，直接返回false
	if A == nil || B == nil {
		return false
	}
	// 2. 定义一个方法，遍历A树，找到 B根节点相同的节点
	// 显示栈，前序遍历
	stack := []*TreeNode{A}
	// 3. 再定义一个方法，用来判断，两个二叉树是否相等
	for len(stack) > 0 {
		// 前序遍历，处理根节点后右子节点进栈保存，去处理左子节点（下一轮的根节点）
		// 根左右
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if node.Val == B.Val {
			if isSub(node, B) {
				return true
			}
		}
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
	}
	return false
}

func isSub(nodeA, nodeB *TreeNode) bool {
	// 递归终止条件, 任意一方达到 末尾，注意这里的判断：细节
	if nodeA == nil || nodeB == nil {
		// 都为 nil 则正确，B为nil也正确，否则返回false
		if nodeA == nodeB || nodeB == nil {
			return true
		}
		return false
	}
	// 不相等直接返回 false， 否则看子节点的结果
	if nodeA.Val != nodeB.Val {
		return false
	}
	left := isSub(nodeA.Left, nodeB.Left)
	right := isSub(nodeA.Right, nodeB.Right)
	return left && right
}
